public class Leetcode {
}
//leetcode:767:重构字符串
class Solution2 {
    public String reorganizeString(String s) {
        int[] hash = new int[26];
        char maxchar = 0;
        int maxcount = 0, n = s.length();
        for(int i = 0; i < n; i++){
            char ch = s.charAt(i);
            //记录出现次数最多的单词和个数
            if(maxcount < ++hash[ch-'a']){
                maxchar = ch;
                maxcount = hash[ch-'a'];
            }
        }
        //如果次数超过了数组的一半那么必定不能排序成功返回""
        if(maxcount > (n+1)/2) return "";

        char[] ret = new char[n];
        int index = 0;

        //按偶数位排序次数最多的
        for(int i = 0; i < maxcount; i++){
            ret[index] = maxchar;
            index += 2;
        }
        //移除元素
        hash[maxchar-'a'] = 0;

        //排序剩余的元素
        for(int i = 0; i < 26; i++){
            for(int j = 0; j < hash[i]; j ++){
                //如果超过为数组长度就回到1位置
                if(index >= n) index = 1;
                ret[index] = (char)(i + 'a');
                index += 2;
            }
        }
        //按字符串返回
        return new String(ret);
    }

}